package class06;

import java.util.ArrayList;
import java.util.List;


public class Code03_PrintAllPermutations {
    //打印字符串的全部序列
    static List<String> PrintAllPermutations(String s) {
        List<String> ans = new ArrayList<>();
        if (s == null || s.isEmpty()) {
            return ans;
        }
        char[] str = s.toCharArray();
        f(str, 0, ans);
        return ans;
    }

    static void f(char[] arr, int index, List<String> ans) {
        if (index == arr.length) {
            ans.add(String.valueOf(arr));
        } else {
            for (int i = index; i < arr.length; i++) {
                swap(arr, i, index);
                f(arr, index + 1, ans);
                swap(arr, i, index);
            }
        }
    }

    public static void swap(char[] chs, int i, int j) {
        char tmp = chs[i];
        chs[i] = chs[j];
        chs[j] = tmp;
    }

    //打印字符串的全部序列并且去重
    static List<String> PrintAllPermutations1(String s) {
        List<String> ans = new ArrayList<>();
        if (s == null || s.isEmpty()) {
            return ans;
        }
        char[] str = s.toCharArray();
        f1(str, 0, ans);
        return ans;
    }

    static void f1(char[] arr, int index, List<String> ans) {
        if (index == arr.length) {
            ans.add(String.valueOf(arr));
        } else {
            boolean[] visited = new boolean[256];
            for (int i = index; i < arr.length; i++) {
                if (!visited[arr[i]]) {
                    visited[arr[i]] = true;
                    swap(arr, i, index);
                    f1(arr, index + 1, ans);
                    swap(arr, i, index);
                }
            }
        }
    }

    public static void main(String[] args) {
        PrintAllPermutations("ABB").forEach(System.out::println);
        System.out.println("=====");
        PrintAllPermutations1("ABB").forEach(System.out::println);
    }
}
